package com.hh.TreeQuestions;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author hanghao
 * @Date 2023/7/18 17:57
 * @Version 1.0
 * 二叉搜索树中的众数
 * easy
 */

public class No501 {
    int count;
    int maxCount;
    List<Integer> reslist;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        reslist = new ArrayList<>();
        count = 0;
        maxCount = 0;
        traversal(root);
        int[] res = new int[reslist.size()];
        for (int i = 0; i < reslist.size(); i++) {
            res[i] = reslist.get(i);
        }
        return res;
    }

    private void traversal(TreeNode root) {
        if(root == null) return;
        //左边
        traversal(root.left);
        //中间
        if(pre == null || root.val != pre.val) {
            count = 1;
        } else {
            count++;
        }
        if(count > maxCount) {
            reslist.clear();
            reslist.add(root.val);
            maxCount = root.val;
        } else if (count == maxCount) {
            reslist.add(root.val);
        }
        pre = root;
        //右边
        traversal(root.right);
    }
}
